package 不同路径;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/4/29 11:58
 * @description:
 */
public class Solution2 {
    public int uniquePaths(int m, int n) {
        // 优化dp数组，降低空间复杂度
        //             dp:      0    1   2   3   4   5   6
        //                 0    1    1   1   1   1   1   1
        //                 1    1    2   3   4   5   6   7
        //                 2    1    3   6   10  15  21  28(answer)

        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        System.out.println(Arrays.toString(dp));
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int curNum = dp[j-1] + dp[j];
                dp[j] = curNum;
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[n-1];
    }

}
